package leetcode_121_140;

import java.util.HashSet;

public class singleNumber_136 {
    /**
     *一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。
     * 找出那个只出现了一次的元素。
     *
     * 必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
     */
    public int singleNumber(int[] nums) {
        /**
         * 自己的常规思路
         * 思路是使用hashSet存储，遇到出现过的数字，直接删除
         * 空间复杂度是 O(n)，不满足题意
         * 7ms
         */
        HashSet<Integer>set=new HashSet<>();
        int count=0;  //使用数字，set集合的remove操作很耗时
        for(int i:nums){
            boolean flag=set.add(i);  //是否已经包含该元素
            count+=flag?i:-i;
        }
        return count;
    }

    public int singleNumber1(int[] nums) {
        /**
         * 高解位运算
         * 1ms
         *
         * 使用位运算。对于这道题，可使用异或运算 ⊕\oplus⊕。异或运算有以下三个性质。
         * 1，任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0=a
         * 2，任何数和其自身做异或运算，结果是 0，即 a ⊕ a=0
         * 3，异或运算满足交换律和结合律
         */
        int res = 0;
        for (int i = 0; i < nums.length; i++)
            res ^= nums[i];
        return res;
    }

    /**
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
     * 请你找出并返回那个只出现了一次的元素。
     *
     * 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
     */
    public int singleNumber2(int[] nums) {
        /**
         * 参考高解，使用数组模拟二进制数字每一位的和的方法
         * 最后每一位模3即可
         */
        int []sum=new int[32];
        for(int i:nums){
            for(int t=0;t<32;t++){
                //i>>t，得到的并不是该数字二进制对应位数的值，而是对应的十进制数字
                // 按位右移对应位数，得到该数字二进制对应位数的值
                if((i>>t & 1) == 1)
                    sum[t]++;
            }
        }
        int ans=0;
        for(int t=0;t<32;t++){
            if (sum[t] % 3 == 1)  //如果该位%3，还等于 1
                ans += 1 << t;  //结果加上该位转为10进制的大小
        }
        return ans;
    }

    public int singleNumber3(int[] nums) {
        /**
         * 高解中的高解
         */
        int ones = 0;  //32位的变量
        int twos = 0;
        //使用 ones 的第 k 位 与 twos 的第 k 位组合起来的两位二进制,表示当前位出现了几次
        for (int i = 0; i < nums.length; ++i)
        {
            //^ 如果相对应位值相同，则结果为0，否则为1
            // ~ 按位取反运算符翻转操作数的每一位

            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;

            //即每一位使用两个32位变量的对应位组合起来表示
            //ones要为1，twos就不能为1，所以是~twos，如果ones  twos同时为1了，就取0
            //00 (+) 1 = 01          -> 后一位   (ones) 0  ^  (nums[i])  1 = 1 & (~twos) 1  = 1
            //                                    前一位   (twos) 0  ^  (nums[i])  1 = 1 & (~ones) 0  = 0      -》01
            //01 (+) 1 = 10
            //10 (+) 1 = 00 ( mod 3)  //出现第三次自动变为0
        }
        return ones;
    }

}
